package leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class LeetCodeMain126 {
    public int minDistance(String word1, String word2) {
        int length1=word1.length();
        int length2=word2.length();
        int[][] dp=new int[length1+1][length2+1];
        for (int i = 1; i <= length1; i++) {
            dp[i][0]=i;
        }
        for (int i = 1; i <= length2; i++) {
            dp[0][i]=i;
        }
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        return dp[length1][length2];
    }
    public int coinChange(int[] coins, int amount) {
        int res = Integer.MAX_VALUE;
        for(int i = 0;i<coins.length;i++){
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(coins[i]);//起点
            int step=dfs(coins,amount,queue);
            if(step!=-1){
                res = Math.min(res,step);
            }
        }
        return (res==Integer.MAX_VALUE)?-1:res;
    }

    private int dfs(int[] coins, int target, Queue<Integer> queue) {
        int steps = 1;
        while(!queue.isEmpty()){
            int sz = queue.size();
            for(int i = 0;i<sz;i++){
                int front =queue.poll();
                if(front == target) return steps;
                if(front>target) continue;
                for(int j = 0;j<coins.length;j++){
                    queue.offer(front+coins[j]);
                }
            }
            steps++;
        }
        return -1;
    }
    public int coinChange2(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j-coins[i]]!=Integer.MAX_VALUE){
                    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }

        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
    int countSum=Integer.MAX_VALUE;
    boolean flag=true;
    public int coinChange1(int[] coins, int amount) {
        Arrays.sort(coins);
        DFS(0,coins,amount,0,coins.length-1);
        return countSum==Integer.MAX_VALUE?-1:countSum;
    }
    public void DFS(int sum,int[] coins,int amount,int count,int startIndex){
        if (sum==amount){
            countSum=Math.min(countSum,count);
            flag=false;
            return;
        }
        for (int i = startIndex; i >= 0&&countSum==Integer.MAX_VALUE; i--) {
            if (sum+coins[i]>amount){
                continue;
            }
            sum+=coins[i];
            count++;
            DFS(sum, coins, amount, count,i);
            sum-=coins[i];
            count--;
        }
    }
}
